package subject.dp;

import java.util.Arrays;

public class coinChange {

    public int coinChange1(int[] coins, int amount) {
        // 1. 初始化最大值（amount+1 作为"无穷大"）
        int max = amount + 1;

        // 2. 创建DP数组（0到amount）
        int[] dp = new int[amount + 1];

        // 3. 初始化DP数组（除0外都设为max）
        Arrays.fill(dp, max);
        dp[0] = 0; // 基础情况

        // 4. 从1到amount计算每个金额
        for (int i = 1; i <= amount; i++) {
            // 尝试每种硬币
            for (int j = 0; j < coins.length; j++) {
                // 5. 如果硬币可用（面值<=当前金额）
                if (coins[j] <= i) {
                    // 6. 关键状态转移：更新最少硬币数
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        // 7. 检查是否有解
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
